114. 二叉树展开为链表

Similar Question

leading to the advanced question

Solution Tips

方案一: 迭代

关键是搞好指针的指向, 还是那个思路, 简化树, 最简单的情况先试着走通就好了

var flatten = function(root) {
    // 前序遍历拼接就好了, 感觉也不是很难呀
    // 当然可以全部 push 完再做拼接
    const stack = [root];
    let dummy = new TreeNode(0);
    let prev = dummy;

    while (stack.length) {
        const node = stack.pop();

        if (node !== null) {
            stack.push(node.right);
            stack.push(node.left);

            prev.right = node;
            prev.left = null;
            prev = node;
        }
    }

    return dummy.right;
};

方案二: 寻找前驱节点 (Morris 遍历)

注意到前序遍历访问各节点的顺序是根节点、左子树、右子树。如果一个节点的左子节点为空，则该节点不需要进行展开操作。如果一个节点的左子节点不为空，则该节点的左子树中的最后一个节点被访问之后，该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点。因此，问题转化成寻找当前节点的前驱节点。

具体做法是，对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。

查看动图

var flatten = function(root) {
    let curr = root;
    while (curr !== null) {
        if (curr.left !== null) {
            const next = curr.left;
            let predecessor = next;
            while (predecessor.right !== null) {
                predecessor = predecessor.right;
            }
            predecessor.right = curr.right;
            curr.left = null;
            curr.right = next;
        }
        curr = curr.right;
    }
};